package leetcode.editor.cn;
 
/**
 * 整数拆分
 * @author qulq
 * @date 2024-07-22 20:45:52
 */
public class T343_IntegerBreak{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T343_IntegerBreak().new Solution();
	 }

	/**
	 * 最后一步：拆分出的最后一个数为j （1 <= j < i）
	 * 那么剩下的 i-j 进行讨论：
	 * 1、i-j就不拆分了，直接就一个数 乘 j
	 * 2、i-j继续拆分，那么就是求整数 i-j 可以拆分的最大乘积，得到子问题！
	 * 所以 dp[i]：整数i拆分成2个及以上的最大乘积！！
	 *
	 * 为什么需要分两个场景？为什么两个的情况无法借助之前的dp项？
	 * 因为之前的dp项最少都拆分为2个数字，再加上现在多出来的值，最少都有3项，所以拆为两个的情况需要单独列出来，并不会与dp[i] = j * dp[i-j] 场景重叠
	 * dp[i] 表示至少拆分成两个！！！
	 * 最少拆分成2个，从dp[2]开始才有意义，所以不考虑dp[0]、dp[1]的初始化
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int integerBreak(int n) {
		int[] dp = new int[n + 1];
		for (int i = 2; i <= n; i++) {
			int curMax = 0;
			for (int j = 1; j < i; j++) {
				curMax = Math.max(curMax, Math.max((i - j) * j, dp[i - j] * j));
			}
			dp[i] = curMax;
		}
		return dp[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}